// https://leetcode.cn/problems/find-peak-element/description/

// 算法思路总结：
// 1. 二分查找寻找数组中的任意峰值元素
// 2. 处理边界情况：单元素数组和首尾峰值
// 3. 根据中点与相邻元素关系判断搜索方向
// 4. 利用局部单调性向更高方向收缩搜索区间
// 5. 时间复杂度：O(log n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int findPeakElement(vector<int>& nums) 
    {
        int m = nums.size();

        if (m == 1) return 0;
        if (nums[0] > nums[1]) return 0;
        if (nums[m - 1] > nums[m - 2]) return m - 1;

        int l = 0, r = m - 1;
        while (l + 1 != r)
        {
            int mid = (l + r) >> 1;
            if (nums[mid] < nums[mid + 1] && nums[mid] > nums[mid - 1])
            {
                l = mid;
            }
            else if (nums[mid] > nums[mid + 1] && nums[mid] < nums[mid - 1])
            {
                r = mid;
            }
            else
            {
                l = mid;
            }
        }

        return l;
    }
};

int main()
{
    vector<int> arr1 = {1,2,3,1}, arr2 = {1,2,1,3,5,6,4};
    Solution sol;

    cout << sol.findPeakElement(arr1) << endl;
    cout << sol.findPeakElement(arr2) << endl;   

    return 0;
}